{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉树中的最大路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中的最大路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>路径</strong> 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 <strong>至多出现一次</strong> 。该路径<strong> 至少包含一个 </strong>节点，且不一定经过根节点。</p>\n",
    "\n",
    "<p><strong>路径和</strong> 是路径中各节点值的总和。</p>\n",
    "\n",
    "<p>给定一个二叉树的根节点 <code>root</code> ，返回其 <strong>最大路径和</strong>，即所有路径上节点值之和的最大值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg\" style=\"width: 322px; height: 182px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>最优路径是 2 -&gt; 1 -&gt; 3 ，路径和为 2 + 1 + 3 = 6</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [-10,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>42\n",
    "<strong>解释：</strong>最优路径是 15 -&gt; 20 -&gt; 7 ，路径和为 15 + 20 + 7 = 42\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目范围是 <code>[1, 3 * 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 124&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/\">https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jC7MId](https://leetcode.cn/problems/jC7MId/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jC7MId](https://leetcode.cn/problems/jC7MId/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[-10,9,20,null,null,15,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = -inf\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            nonlocal ans\n",
    "            if node is None:\n",
    "                return 0  # 没有节点，和为 0\n",
    "            l_val = dfs(node.left)  # 左子树最大链和\n",
    "            r_val = dfs(node.right)  # 右子树最大链和\n",
    "            node_val = max(node.val, node.val+l_val, node.val+r_val)\n",
    "            ans = max(ans, node_val, node.val+l_val+r_val)  # 两条链拼成路径\n",
    "            return node_val  # 当前子树最大链和\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        ans = -inf\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            lv = max(0,dfs(root.left) )\n",
    "            rv = max(0,dfs(root.right))\n",
    "            nonlocal ans\n",
    "            ans = max(lv+rv+root.val,ans)\n",
    "            return max(lv,rv)+root.val\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class SumScore:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.value = 0\n",
    "\n",
    "\n",
    "def find_max_path(root, sum: SumScore):\n",
    "    if root is None:\n",
    "        return 0\n",
    "\n",
    "    left = find_max_path(root.left, sum)\n",
    "    right = find_max_path(root.right, sum)\n",
    "\n",
    "    sum.value = max(sum.value, left + right + root.val)\n",
    "    return max(max(left, right) + root.val, 0, root.val)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        sum_score = SumScore()\n",
    "        sum_score.value = root.val\n",
    "        find_max_path(root, sum_score)\n",
    "        return sum_score.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxSum = float(\"-inf\")\n",
    "\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def maxGain(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            leftGain = max(maxGain(node.left), 0)\n",
    "            rightGain = max(maxGain(node.right), 0)\n",
    "            \n",
    "            priceNewpath = node.val + leftGain + rightGain\n",
    "            \n",
    "            self.maxSum = max(self.maxSum, priceNewpath)\n",
    "        \n",
    "            return node.val + max(leftGain, rightGain)\n",
    "   \n",
    "        maxGain(root)\n",
    "        return self.maxSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        self.res=-1001\n",
    "        self.search(root)\n",
    "        return self.res\n",
    "\n",
    "    def search(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        left = self.search(node.left)\n",
    "        left = max(left, 0)\n",
    "        right = self.search(node.right)\n",
    "        right = max(right, 0)\n",
    "        self.res=max(self.res, node.val+left+right)\n",
    "        return node.val+max(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        ans = root.val\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = max(0, dfs(node.left))\n",
    "            r = max(0, dfs(node.right))\n",
    "            ans = max(ans, l+r+node.val)\n",
    "            return max(l, r) + node.val\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    res = -1000\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return 0\n",
    "            \n",
    "            left_val = max(0, dfs(node.left))\n",
    "            right_val = max(0, dfs(node.right))\n",
    "\n",
    "            price = node.val + left_val + right_val\n",
    "            self.res = max(price, self.res)\n",
    "\n",
    "            return node.val + max(left_val, right_val)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class SumScore:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.value = 0\n",
    "\n",
    "\n",
    "def find_max_path(root, sum: SumScore):\n",
    "    if root is None:\n",
    "        return 0\n",
    "\n",
    "    left = find_max_path(root.left, sum)\n",
    "    right = find_max_path(root.right, sum)\n",
    "\n",
    "    sum.value = max(sum.value, left + right + root.val)\n",
    "    return max(max(left, right) + root.val, 0, root.val)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        sum_score = SumScore()\n",
    "        sum_score.value = root.val\n",
    "        find_max_path(root, sum_score)\n",
    "        return sum_score.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class SumScore:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.value = 0\n",
    "\n",
    "\n",
    "def find_max_path(root, sum: SumScore):\n",
    "    if root is None:\n",
    "        return 0\n",
    "\n",
    "    left = find_max_path(root.left, sum)\n",
    "    right = find_max_path(root.right, sum)\n",
    "\n",
    "    sum.value = max(sum.value, left + right + root.val)\n",
    "    return max(max(left, right) + root.val, 0, root.val)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        sum_score = SumScore()\n",
    "        sum_score.value = root.val\n",
    "        find_max_path(root, sum_score)\n",
    "        return sum_score.value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxSum = float('-inf')\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def dfs(node):\n",
    "            if not node: return 0\n",
    "            leftgain = max(dfs(node.left), 0)\n",
    "            rightgain = max(dfs(node.right), 0)\n",
    "            priceNewpath = node.val + leftgain + rightgain\n",
    "            self.maxSum = max(self.maxSum, priceNewpath)\n",
    "            return node.val + max(leftgain, rightgain)\n",
    "        dfs(root)\n",
    "        return self.maxSum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class SumScore:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.value = 0\n",
    "\n",
    "\n",
    "def find_max_path(root, sum: SumScore):\n",
    "    if root is None:\n",
    "        return 0\n",
    "\n",
    "    left = max(find_max_path(root.left, sum), 0)\n",
    "    right = max(find_max_path(root.right, sum), 0)\n",
    "\n",
    "    sum.value = max(sum.value, left + right + root.val)\n",
    "    return max(max(left, right) + root.val, 0, root.val)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        sum_score = SumScore()\n",
    "        sum_score.value = root.val\n",
    "        find_max_path(root, sum_score)\n",
    "        return sum_score.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        self.res = -inf\n",
    "\n",
    "        def maxPath(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            left_max = max(maxPath(root.left), 0) # max with 0 is important here!\n",
    "            right_max = max(maxPath(root.right), 0)\n",
    "\n",
    "            self.res = max(self.res, left_max + root.val + right_max)\n",
    "            return root.val + max(left_max, right_max)\n",
    "        \n",
    "        n = maxPath(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        max_val = float('-inf')\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left = max(dfs(root.left), 0 )\n",
    "            right = max(dfs(root.right), 0)\n",
    "            print('left=', left)\n",
    "            print('right=', right)\n",
    "            nonlocal max_val\n",
    "            max_val = max(max_val, root.val+left+right)\n",
    "            return max(left, right) + root.val\n",
    "        dfs(root)\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 思路：\n",
    "# 1 定义ans\n",
    "# 2 使用dfs,更新左链l_val和右链r_val的值\n",
    "# 3 nonlocal ans,合并左右两条链路ans = max(ans, l_val+ r_val+node.val)\n",
    "# 4 返回子树的最大和 max(max(l_val+r_val+node.val),0)\n",
    "# global和nonlocal的区别\n",
    "# global全局变量，nonlocal是承接上一函数的局部变量，不能用于底层的函数中。\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        ans = -inf # 定义ans全局变量\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0 # 没有节点，和为0\n",
    "            l_val = dfs(node.left) # 左子树的最大链和\n",
    "            r_val = dfs(node.right) # 右子树的最大链和\n",
    "            nonlocal ans # 定义局部的ans,可以继承上一级函数的值\n",
    "            ans = max(ans,l_val + r_val + node.val) # 两条链拼成路径\n",
    "            return max(max(l_val, r_val) + node.val,0) # 选当前子树最大链和\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        ans = -inf\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            nonlocal ans\n",
    "            ans = max(ans, l+r+node.val)\n",
    "            # 当前节点值的和可能是负数，如果是负数把该值置为0，相当于不要当前节点\n",
    "            return max(max(l, r) + node.val, 0)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        ans = -inf\n",
    "        def recurse(root):\n",
    "            nonlocal ans\n",
    "            if  root == None:\n",
    "                return 0\n",
    "            lv, rv = recurse(root.left), recurse(root.right)\n",
    "            ans = max(ans, lv + rv + root.val)\n",
    "            return max(max(lv, rv) + root.val, 0)\n",
    "        recurse(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxSum = -inf\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        # ans = -inf\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0  # 没有节点，和为 0\n",
    "            l_val = dfs(node.left)  # 左子树最大链和\n",
    "            r_val = dfs(node.right)  # 右子树最大链和\n",
    "            # nonlocal ans\n",
    "            self.maxSum = max(self.maxSum, l_val + r_val + node.val)  # 两条链拼成路径\n",
    "            return max(max(l_val, r_val) + node.val, 0)  # 当前子树最大链和\n",
    "        dfs(root)\n",
    "        return self.maxSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        self.res = -inf\n",
    "\n",
    "        def maxPath(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            left_max = max(maxPath(root.left), 0) # max with 0 is important here!\n",
    "            right_max = max(maxPath(root.right), 0)\n",
    "\n",
    "            self.res = max(self.res, left_max + root.val + right_max)\n",
    "            return root.val + max(left_max, right_max)\n",
    "        \n",
    "        n = maxPath(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        self.ans = float('-inf')\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if not root.left and not root.right:\n",
    "                self.ans = max(self.ans, root.val)\n",
    "                return max(0, root.val)\n",
    "            if root.left or root.right:\n",
    "                l = dfs(root.left)\n",
    "                r = dfs(root.right)\n",
    "                self.ans = max(self.ans, l + r + root.val)\n",
    "                return max(0, l + root.val, r + root.val)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        INF=-9999999999\n",
    "        self.maxsum=INF\n",
    "        def func(root):\n",
    "            leftsum=0\n",
    "            rightsum=0\n",
    "            if root.left:\n",
    "                leftsum=func(root.left)\n",
    "            if root.right:\n",
    "                rightsum=func(root.right)\n",
    "            ans=root.val\n",
    "            if rightsum>0:\n",
    "                ans+=rightsum\n",
    "            if leftsum>0:\n",
    "                ans+=leftsum\n",
    "            self.maxsum=max(ans,self.maxsum)\n",
    "            print(root.val,root.val+rightsum,root.val+leftsum)\n",
    "            return max(root.val,root.val+rightsum,root.val+leftsum)\n",
    "        func(root)\n",
    "        return self.maxsum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def traversal(cur_root):\n",
    "            if not cur_root:\n",
    "                return None,0\n",
    "            \n",
    "\n",
    "            left_max, left_root_max = traversal(cur_root.left)\n",
    "            right_max, right_root_max = traversal(cur_root.right)\n",
    "\n",
    "            cur_max = [cur_root.val, cur_root.val + left_root_max+right_root_max]\n",
    "            if (left_max is not None):\n",
    "                cur_max.append(left_max)\n",
    "            if right_max is not None:\n",
    "                cur_max.append(right_max)\n",
    "\n",
    "            cur_root_max = cur_root.val+max(left_root_max, right_root_max)\n",
    "            cur_max.append(cur_root_max)\n",
    "\n",
    "            if max(left_root_max, right_root_max) <0:\n",
    "                cur_root_max = cur_root.val\n",
    "\n",
    "            # print(cur_root.val, cur_max, cur_root_max)\n",
    "            return max(cur_max), cur_root_max\n",
    "        \n",
    "        max_list = traversal(root)\n",
    "        return max(max_list)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.max = -float(\"inf\")\n",
    "\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            left_gain = max(0, dfs(root.left))\n",
    "            right_gain = max(0, dfs(root.right))\n",
    "            self.max = max(self.max, root.val + left_gain + right_gain)\n",
    "\n",
    "            return root.val + max(left_gain, right_gain)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.max\n",
    "\n",
    "\n",
    "    # def __init__(self):\n",
    "    #     self.path_sum = -float(\"inf\")\n",
    "    # def maxPathSum(self, root: TreeNode) -> int:\n",
    "    #     def path_gain(root):\n",
    "    #         if not root: return 0\n",
    "    #         left_gain = max(0, path_gain(root.left))\n",
    "    #         right_gain = max(0, path_gain(root.right))\n",
    "\n",
    "    #         cur_gain = root.val + left_gain + right_gain\n",
    "    #         self.path_sum = max(self.path_sum, cur_gain)\n",
    "\n",
    "    #         return root.val + max(left_gain, right_gain)\n",
    "        \n",
    "    #     path_gain(root)\n",
    "    #     return self.path_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxSum = -inf\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        # ans = -inf\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0  # 没有节点，和为 0\n",
    "            l_val = max(dfs(node.left),0)  # 左子树最大链和\n",
    "            r_val = max(dfs(node.right),0)  # 右子树最大链和\n",
    "            # nonlocal ans\n",
    "            self.maxSum = max(self.maxSum, l_val + r_val + node.val)  # 两条链拼成路径\n",
    "            return max(l_val,r_val)+node.val\n",
    "            # return max(max(l_val, r_val) + node.val, 0)  # 当前子树最大链和\n",
    "        dfs(root)\n",
    "        return self.maxSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    max_sum = None\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.sum_of_path_helper(root)\n",
    "        return self.max_sum\n",
    "\n",
    "    def sum_of_path_helper(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left = self.sum_of_path_helper(root.left)\n",
    "        right = self.sum_of_path_helper(root.right)\n",
    "        self.max_sum = max(self.max_sum, max(max(left + right + root.val, root.val), max(left, right) + root.val)) if self.max_sum is not None else max(max(left + right + root.val, root.val), max(left, right) + root.val)\n",
    "        return max(max(left, right) + root.val, root.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        # 递归\n",
    "        # 包含自己的左边最大值，包含自己的右边最大值，最大值（可能包含，也可能不包含）\n",
    "        def dfs(node):\n",
    "            if not node.left and not node.right:\n",
    "                return node.val, node.val, node.val\n",
    "            \n",
    "            if node.left and node.right:\n",
    "                ll, lr, lm = dfs(node.left)\n",
    "                rl, rr, rm = dfs(node.right)\n",
    "                l = max(ll, lr, 0) + node.val\n",
    "                r = max(rl, rr, 0) + node.val\n",
    "                m = max(lm, rm, l + r - node.val)\n",
    "                return l, r, m\n",
    "            \n",
    "            if node.left:\n",
    "                ll, lr, lm = dfs(node.left)\n",
    "                l = max(ll, lr, 0) + node.val\n",
    "                r = node.val\n",
    "                m = max(lm, l)\n",
    "                return l, r, m\n",
    "\n",
    "            rl, rr, rm = dfs(node.right)\n",
    "            l = node.val\n",
    "            r = max(rl, rr, 0) + node.val\n",
    "            m = max(rm, r)\n",
    "            return l, r, m\n",
    "        \n",
    "        return dfs(root)[2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        return max(self.dfs(root))\n",
    "    \n",
    "    def dfs(self, root):\n",
    "        if root == None:\n",
    "            return float('-inf'), float('-inf')\n",
    "        \n",
    "        leftY, leftN = self.dfs(root.left)\n",
    "        rightY, rightN = self.dfs(root.right)\n",
    "        yes = max(root.val, root.val + leftY, root.val + rightY)\n",
    "        no = max(leftY, leftN, rightY, rightN, root.val + leftY + rightY)\n",
    "        return yes, no"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        ans = float('-inf')\n",
    "        def DFS(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return float('-inf')\n",
    "            l = DFS(node.left)\n",
    "            r = DFS(node.right)\n",
    "            c = node.val\n",
    "            ans = max(ans, l, r, l + c, r + c, l + r + c, c)\n",
    "            return max(c, l + c, r + c)\n",
    "        \n",
    "        DFS(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def M1(self, root: TreeNode) -> int:\r\n",
    "        '''\r\n",
    "        路径最大和\r\n",
    "        子问题: 以root为节点的最大值, 单条最大\r\n",
    "            必须包含 左节点的 的最大值路径 | 都是单条的\r\n",
    "\r\n",
    "        解: 在状态的过程中 记录 以下情况中的最大值: \r\n",
    "            1. 只有根节点; \r\n",
    "            2. 根 + 右; \r\n",
    "            3. 根 + 左; \r\n",
    "            4. 根 + 左 + 右\r\n",
    "        '''\r\n",
    "        min_value = -1001\r\n",
    "        ans = [min_value]\r\n",
    "        # @cache\r\n",
    "        def findMax(root: TreeNode):\r\n",
    "            ''' \r\n",
    "            包含当前节点的最大值, 单条路径\r\n",
    "            '''\r\n",
    "            # 空节点\r\n",
    "            if not root: return min_value\r\n",
    "            # 叶子: 自己独自成一条路径 | 该情况直接包括在下方的else过程中\r\n",
    "            # if not root.left and not root.right:\r\n",
    "            #     ans[0] = max(ans[0], root.val)\r\n",
    "            #     return root.val\r\n",
    "            # 非叶子节点\r\n",
    "            leftMax = findMax(root.left)\r\n",
    "            rightMax = findMax(root.right)\r\n",
    "            \r\n",
    "            # 最大值的可能来源: 1. 只有根节点; 2. 根 + 右; 3. 根 + 左; 4. 根 + 左 + 右\r\n",
    "            if leftMax >= 0 and rightMax >= 0:\r\n",
    "                ans[0] = max(ans[0], root.val + leftMax + rightMax)\r\n",
    "                return max(leftMax, rightMax) + root.val\r\n",
    "            elif leftMax < 0 and rightMax >= 0:\r\n",
    "                ans[0] = max(ans[0], rightMax + root.val)\r\n",
    "                return rightMax + root.val\r\n",
    "            elif leftMax >= 0 and rightMax < 0:\r\n",
    "                ans[0] = max(ans[0], leftMax + root.val)\r\n",
    "                return leftMax + root.val\r\n",
    "            else: # < < 0\r\n",
    "                # print(leftMax, rightMax)\r\n",
    "                ans[0] = max(ans[0], root.val)\r\n",
    "                return root.val\r\n",
    "            \r\n",
    "            # 老版本\r\n",
    "            # 最大值的可能来源: 1. 只有根节点; 2. 根 + 右; 3. 根 + 左; 4. 根 + 左 + 右\r\n",
    "            ans[0] = max(ans[0], root.val, root.val + max(leftMax + rightMax, leftMax, rightMax))\r\n",
    "            # 返回包含root的单侧最大: 1. 只有根节点; 2. 根+ 左; 3. 根 + 右; \r\n",
    "            return max(max(leftMax, rightMax) + root.val, root.val)\r\n",
    "\r\n",
    "        # 不用去遍历每个节点?\r\n",
    "        # 因为子问题的状态过程中, 已经遍历了每个节点, 在其中进行过程的记录即可\r\n",
    "        # def traversal(root: TreeNode):\r\n",
    "        #     # 遍历每个节点\r\n",
    "        #     if not root: return\r\n",
    "        #     findMax(root)\r\n",
    "        #     traversal(root.left)\r\n",
    "        #     traversal(root.right)\r\n",
    "        # traversal(root)\r\n",
    "        findMax(root)\r\n",
    "        # print(findMax.cache_info())\r\n",
    "        return ans[0]\r\n",
    "    \r\n",
    "    def M11(self, root: TreeNode) -> int:\r\n",
    "        '''\r\n",
    "        路径最大和\r\n",
    "        子问题: 以root为节点的最大值, 单条最大\r\n",
    "            必须包含 左节点的 的最大值路径 | 都是单条的\r\n",
    "\r\n",
    "        解: 在状态的过程中 记录 以下情况中的最大值: \r\n",
    "            1. 只有根节点; \r\n",
    "            2. 根 + 右; \r\n",
    "            3. 根 + 左; \r\n",
    "            4. 根 + 左 + 右\r\n",
    "        '''\r\n",
    "        min_value = -1001\r\n",
    "        ans = min_value\r\n",
    "        # @cache\r\n",
    "        def findMax(root: TreeNode):\r\n",
    "            ''' \r\n",
    "            包含当前节点的最大值, 单条路径\r\n",
    "            '''\r\n",
    "            nonlocal ans\r\n",
    "            # 空节点: 返回最小值\r\n",
    "            if not root: return min_value\r\n",
    "            leftMax = findMax(root.left)\r\n",
    "            rightMax = findMax(root.right)\r\n",
    "            \r\n",
    "            # 最大值的可能来源: 1. 只有根节点; 2. 根 + 右; 3. 根 + 左; 4. 根 + 左 + 右\r\n",
    "            if leftMax >= 0 and rightMax >= 0:\r\n",
    "                ans = max(ans, root.val + leftMax + rightMax)\r\n",
    "                return max(leftMax, rightMax) + root.val\r\n",
    "            elif leftMax < 0 and rightMax >= 0:\r\n",
    "                ans = max(ans, rightMax + root.val)\r\n",
    "                return rightMax + root.val\r\n",
    "            elif leftMax >= 0 and rightMax < 0:\r\n",
    "                ans = max(ans, leftMax + root.val)\r\n",
    "                return leftMax + root.val\r\n",
    "            else: # leftMax < 0 and rightMax < 0\r\n",
    "                ans = max(ans, root.val)\r\n",
    "                return root.val\r\n",
    "            \r\n",
    "            # 老版本\r\n",
    "            # 最大值的可能来源: 1. 只有根节点; 2. 根 + 右; 3. 根 + 左; 4. 根 + 左 + 右\r\n",
    "            ans[0] = max(ans[0], root.val, root.val + max(leftMax + rightMax, leftMax, rightMax))\r\n",
    "            # 返回包含root的单侧最大: 1. 只有根节点; 2. 根+ 左; 3. 根 + 右; \r\n",
    "            return max(max(leftMax, rightMax) + root.val, root.val)\r\n",
    "        \r\n",
    "        findMax(root)\r\n",
    "        return ans\r\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\r\n",
    "        return self.M11(root=root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        self.node_dict = {}\n",
    "        self.ans = float('-inf')\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, node):\n",
    "        left_sum, right_sum = 0, 0\n",
    "        if node.left:\n",
    "            left_sum = self.dfs(node.left)\n",
    "        if node.right:\n",
    "            right_sum = self.dfs(node.right)\n",
    "\n",
    "        cur_max_sum = max([node.val, node.val + left_sum, node.val + right_sum])\n",
    "        self.node_dict[node] = cur_max_sum\n",
    "\n",
    "        self.ans = max([self.ans, cur_max_sum, left_sum + right_sum + node.val])\n",
    "\n",
    "        return cur_max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def M1(self, root: TreeNode) -> int:\r\n",
    "        '''\r\n",
    "        路径最大和\r\n",
    "        子问题: 以root为节点的最大值, 单条最大\r\n",
    "            必须包含 左节点的 的最大值路径 | 都是单条的\r\n",
    "\r\n",
    "        解: 在状态的过程中 记录 以下情况中的最大值: \r\n",
    "            1. 只有根节点; \r\n",
    "            2. 根 + 右; \r\n",
    "            3. 根 + 左; \r\n",
    "            4. 根 + 左 + 右\r\n",
    "        '''\r\n",
    "        min_value = -1001\r\n",
    "        ans = [min_value]\r\n",
    "        # @cache\r\n",
    "        def findMax(root: TreeNode):\r\n",
    "            ''' \r\n",
    "            包含当前节点的最大值, 单条路径\r\n",
    "            '''\r\n",
    "            # 空节点\r\n",
    "            if not root: return min_value\r\n",
    "            # 叶子: 自己独自成一条路径 | 该情况直接包括在下方的else过程中\r\n",
    "            # if not root.left and not root.right:\r\n",
    "            #     ans[0] = max(ans[0], root.val)\r\n",
    "            #     return root.val\r\n",
    "            # 非叶子节点\r\n",
    "            leftMax = findMax(root.left)\r\n",
    "            rightMax = findMax(root.right)\r\n",
    "            \r\n",
    "            # 最大值的可能来源: 1. 只有根节点; 2. 根 + 右; 3. 根 + 左; 4. 根 + 左 + 右\r\n",
    "            if leftMax >= 0 and rightMax >= 0:\r\n",
    "                ans[0] = max(ans[0], root.val + leftMax + rightMax)\r\n",
    "                return max(leftMax, rightMax) + root.val\r\n",
    "            elif leftMax < 0 and rightMax >= 0:\r\n",
    "                ans[0] = max(ans[0], rightMax + root.val)\r\n",
    "                return rightMax + root.val\r\n",
    "            elif leftMax >= 0 and rightMax < 0:\r\n",
    "                ans[0] = max(ans[0], leftMax + root.val)\r\n",
    "                return leftMax + root.val\r\n",
    "            else: # < < 0\r\n",
    "                # print(leftMax, rightMax)\r\n",
    "                ans[0] = max(ans[0], root.val)\r\n",
    "                return root.val\r\n",
    "            \r\n",
    "            # 老版本\r\n",
    "            # 最大值的可能来源: 1. 只有根节点; 2. 根 + 右; 3. 根 + 左; 4. 根 + 左 + 右\r\n",
    "            ans[0] = max(ans[0], root.val, root.val + max(leftMax + rightMax, leftMax, rightMax))\r\n",
    "            # 返回包含root的单侧最大: 1. 只有根节点; 2. 根+ 左; 3. 根 + 右; \r\n",
    "            return max(max(leftMax, rightMax) + root.val, root.val)\r\n",
    "\r\n",
    "        # 不用去遍历每个节点?\r\n",
    "        # 因为子问题的状态过程中, 已经遍历了每个节点, 在其中进行过程的记录即可\r\n",
    "        # def traversal(root: TreeNode):\r\n",
    "        #     # 遍历每个节点\r\n",
    "        #     if not root: return\r\n",
    "        #     findMax(root)\r\n",
    "        #     traversal(root.left)\r\n",
    "        #     traversal(root.right)\r\n",
    "        # traversal(root)\r\n",
    "        findMax(root)\r\n",
    "        # print(findMax.cache_info())\r\n",
    "        return ans[0]\r\n",
    "    \r\n",
    "    def M11(self, root: TreeNode) -> int:\r\n",
    "        ''' 优化 一次遍历 和 缓存的过程\r\n",
    "        '''\r\n",
    "        min_value = -1001\r\n",
    "        ans = min_value\r\n",
    "        # @cache\r\n",
    "        def findMax(root: TreeNode):\r\n",
    "            ''' \r\n",
    "            包含当前节点的最大值, 单条路径\r\n",
    "            '''\r\n",
    "            nonlocal ans\r\n",
    "            # 空节点: 返回最小值\r\n",
    "            if not root: return min_value\r\n",
    "            leftMax = findMax(root.left)\r\n",
    "            rightMax = findMax(root.right)\r\n",
    "            \r\n",
    "            # 最大值的可能来源: 1. 只有根节点; 2. 根 + 右; 3. 根 + 左; 4. 根 + 左 + 右\r\n",
    "            if leftMax >= 0 and rightMax >= 0:\r\n",
    "                ans = max(ans, root.val + leftMax + rightMax)\r\n",
    "                return max(leftMax, rightMax) + root.val\r\n",
    "            elif leftMax < 0 and rightMax >= 0:\r\n",
    "                ans = max(ans, rightMax + root.val)\r\n",
    "                return rightMax + root.val\r\n",
    "            elif leftMax >= 0 and rightMax < 0:\r\n",
    "                ans = max(ans, leftMax + root.val)\r\n",
    "                return leftMax + root.val\r\n",
    "            else: # leftMax < 0 and rightMax < 0\r\n",
    "                ans = max(ans, root.val)\r\n",
    "                return root.val\r\n",
    "        \r\n",
    "        findMax(root)\r\n",
    "        return ans\r\n",
    "    def M12(self, root: TreeNode) -> int:\r\n",
    "        ''' 优化那么多的判断代码\r\n",
    "        '''\r\n",
    "        min_value = -1001\r\n",
    "        ans = min_value\r\n",
    "        # @cache\r\n",
    "        def findMax(root: TreeNode):\r\n",
    "            ''' \r\n",
    "            包含当前节点的最大值, 单条路径\r\n",
    "            '''\r\n",
    "            nonlocal ans\r\n",
    "            # 空节点: 返回最小值\r\n",
    "            if not root: return min_value\r\n",
    "            # @优化: 保证都>=0, =0时 包含了不取left or right的情况\r\n",
    "            leftMax = max(findMax(root.left), 0)\r\n",
    "            rightMax = max(findMax(root.right), 0)\r\n",
    "            \r\n",
    "            # 最大值的可能来源: 1. 只有根节点; 2. 根 + 右; 3. 根 + 左; 4. 根 + 左 + 右\r\n",
    "            # 保留该情况即可 if leftMax >= 0 and rightMax >= 0: \r\n",
    "            ans = max(ans, root.val + leftMax + rightMax)\r\n",
    "            return max(leftMax, rightMax) + root.val\r\n",
    "        \r\n",
    "        findMax(root)\r\n",
    "        return ans\r\n",
    "    def TopV(self, root: TreeNode) -> int:\r\n",
    "        def maxPathSum(root: Optional[TreeNode]) -> int:\r\n",
    "            ans = -float('inf')\r\n",
    "            def dfs(node: Optional[TreeNode]) -> int:\r\n",
    "                if node is None:\r\n",
    "                    return 0  # 没有节点，和为 0\r\n",
    "                l_val = dfs(node.left)  # 左子树最大链和\r\n",
    "                r_val = dfs(node.right)  # 右子树最大链和\r\n",
    "                nonlocal ans\r\n",
    "                ans = max(ans, l_val + r_val + node.val)  # 两条链拼成路径\r\n",
    "                return max(max(l_val, r_val) + node.val, 0)  # 当前子树最大链和\r\n",
    "            dfs(root)\r\n",
    "            return ans\r\n",
    "        return maxPathSum(root)\r\n",
    "        \r\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\r\n",
    "        return self.M12(root=root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0,-10000\n",
    "            l_max_path, l_res = dfs(node.left)\n",
    "            r_max_path, r_res = dfs(node.right)\n",
    "            max_path = max(l_max_path,r_max_path) + node.val\n",
    "            max_path = max(max_path,node.val)\n",
    "            # res = 0\n",
    "            # print(r_res)\n",
    "            res = max([l_res, r_res, l_max_path+r_max_path+node.val, node.val, node.val+l_max_path,node.val+r_max_path])\n",
    "            return max_path,res\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def f(x, maxSum):\n",
    "            if not x:\n",
    "                return 0\n",
    "            maxLeft = []\n",
    "            left = max(0, f(x.left, maxLeft))\n",
    "            maxRight = []\n",
    "            right = max(0, f(x.right, maxRight))\n",
    "            \n",
    "\n",
    "            if max(maxLeft, maxRight):\n",
    "                maxSum.append(max(maxLeft, maxRight)[0])\n",
    "\n",
    "            if maxSum:\n",
    "                maxSum[0] = max(maxSum[0], right + left + x.val)\n",
    "            else:\n",
    "                maxSum.append(x.val)\n",
    "            # maxSum[0] = max(maxSum[0], x.val)\n",
    "            # print(maxLeft, left, maxRight, right, maxSum)\n",
    "            return x.val + max(right, left)\n",
    "        ans = []\n",
    "        print(f(root,ans))\n",
    "        return max(f(root, ans), ans[0])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    ans = 0\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.ans = float('-inf')\n",
    "\n",
    "        def helper(node: TreeNode):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left_max = helper(node.left)\n",
    "            right_max = helper(node.right)\n",
    "            self.ans = max(self.ans, left_max + right_max + node.val, right_max + node.val, left_max + node.val, node.val)\n",
    "            return max(left_max, right_max, 0) + node.val\n",
    "        helper(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        self.ans=-math.inf\n",
    "        def dfs(T,up):\n",
    "            if not T:\n",
    "                return 0\n",
    "            l,r=dfs(T.left,max(up+T.val,T.val)),dfs(T.right,max(up+T.val,T.val))\n",
    "            self.ans=max(self.ans,T.val,T.val+up,T.val+l,T.val+r,T.val+up+l,T.val+up+r,T.val+l+r)\n",
    "            return max(T.val,l+T.val,r+T.val)\n",
    "        dfs(root,-math.inf)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional, Dict\n",
    "\n",
    "\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.best = None\n",
    "\n",
    "    def value(self, root: TreeNode, profit: Dict) -> int:\n",
    "        assert root is not None\n",
    "        if root.left is None:\n",
    "            if root.right is None:\n",
    "                profit[root] = root.val\n",
    "            else:\n",
    "                rv = self.value(root.right, profit)\n",
    "                if rv > 0:\n",
    "                    profit[root] = rv + root.val\n",
    "                else:\n",
    "                    profit[root] = root.val\n",
    "        else:\n",
    "            if root.right is None:\n",
    "                lv = self.value(root.left, profit)\n",
    "                if lv > 0:\n",
    "                    profit[root] = lv + root.val\n",
    "                else:\n",
    "                    profit[root] = root.val\n",
    "            else:\n",
    "                lv = self.value(root.left, profit)\n",
    "                rv = self.value(root.right, profit)\n",
    "                v = max(lv, rv)\n",
    "                if v > 0:\n",
    "                    profit[root] = v + root.val\n",
    "                else:\n",
    "                    profit[root] = root.val\n",
    "\n",
    "        return profit[root]\n",
    "\n",
    "    def traverse(self, root: TreeNode, profit: Dict):\n",
    "        assert root is not None\n",
    "        if root.left is not None:\n",
    "            self.traverse(root.left, profit)\n",
    "        if root.right is not None:\n",
    "            self.traverse(root.right, profit)\n",
    "        if root.left is None:\n",
    "            if root.right is None:\n",
    "                current = root.val\n",
    "                if current > self.best:\n",
    "                    self.best = current\n",
    "            else:\n",
    "                current = root.val\n",
    "                if profit[root.right] > 0:\n",
    "                    current += profit[root.right]\n",
    "                if current > self.best:\n",
    "                    self.best = current\n",
    "        else:\n",
    "            if root.right is None:\n",
    "                current = root.val\n",
    "                if profit[root.left] > 0:\n",
    "                    current += profit[root.left]\n",
    "                if current > self.best:\n",
    "                    self.best = current\n",
    "            else:\n",
    "                current = root.val\n",
    "                if profit[root.left] > 0:\n",
    "                    current += profit[root.left]\n",
    "                if profit[root.right] > 0:\n",
    "                    current += profit[root.right]\n",
    "                if current > self.best:\n",
    "                    self.best = current\n",
    "\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        profit = {}\n",
    "        self.value(root, profit)\n",
    "        self.best = -10000\n",
    "        self.traverse(root, profit)\n",
    "        return self.best\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def cal(root):\n",
    "            left=right=-math.inf\n",
    "            if root.left:\n",
    "                left = cal(root.left)\n",
    "            if root.right:\n",
    "                right = cal(root.right)\n",
    "            self.result = max(self.result,root.val,left+root.val,right+root.val,left+right+root.val) \n",
    "            if root.left is None and root.right is None:\n",
    "                return root.val\n",
    "            return max(left+root.val,right+root.val,root.val)\n",
    "        self.result = -math.inf\n",
    "        cal(root)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "\n",
    "        self.ans = None\n",
    "\n",
    "        def dfs(node):\n",
    "            \n",
    "            curr_max = node.val\n",
    "\n",
    "            left_max = node.val\n",
    "            if node.left:\n",
    "                ll, lr = dfs(node.left)\n",
    "                curr_max += max(ll, lr, 0)\n",
    "                left_max = max(left_max, node.val + ll)\n",
    "                left_max = max(left_max, node.val + lr)\n",
    "            \n",
    "            right_max = node.val\n",
    "            if node.right:\n",
    "                rl, rr = dfs(node.right)\n",
    "                curr_max += max(rl, rr, 0)\n",
    "                right_max = max(right_max, node.val + rl)\n",
    "                right_max = max(right_max, node.val + rr)\n",
    "            \n",
    "            # print(node.val, left_max, right_max, curr_max)\n",
    "            self.ans = curr_max if self.ans is None else max(self.ans, curr_max)\n",
    "            return left_max, right_max\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 时间复杂度：O(n)， 空间复杂度：O(n). 深度优先遍历，后序遍历\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        maxSum = [float('-inf')]\n",
    "        self.dfs(root, maxSum)\n",
    "        return maxSum[0]\n",
    "    \n",
    "    def dfs(self, root, maxSum):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        maxSumLeft = [float('-inf')]\n",
    "        left = max(0, self.dfs(root.left, maxSumLeft))  # 左子树路径节点值节点值之和的最大值\n",
    "\n",
    "        maxSumRight = [float('-inf')]\n",
    "        right = max(0, self.dfs(root.right, maxSumRight)) # 右子树路径节点值节点值之和的最大值\n",
    "\n",
    "        maxSum[0] = max(maxSumLeft[0], maxSumRight[0])\n",
    "        maxSum[0] = max(maxSum[0], left + right + root.val)  # 三者比较取其大\n",
    "        return root.val + max(left, right) # 最后返回经过根节点路径的节点值之和\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def dfs(root,maxs):\n",
    "            if root==None:\n",
    "                return 0\n",
    "            mleft = {0:float(\"-inf\")}\n",
    "            mright = {0:float(\"-inf\")}\n",
    "            left = max(0, dfs(root.left,mleft))\n",
    "            right = max(0, dfs(root.right,mright))\n",
    "\n",
    "            maxs[0]=max(mleft[0],mright[0])\n",
    "            maxs[0] = max(maxs[0], root.val+left+right)\n",
    "            return root.val + max(left,right)\n",
    "        maxs = {0:0}\n",
    "        dfs(root,maxs)\n",
    "        return maxs[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def dfs(root, maxSum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            maxSumleft = [-1001]\n",
    "            left = max(0, dfs(root.left, maxSumleft))\n",
    "            maxSumright = [-1001]\n",
    "            right = max(0, dfs(root.right, maxSumright))\n",
    "            maxSum[0] = max(maxSumleft[0], maxSumright[0])\n",
    "            maxSum[0] = max(maxSum[0], root.val+left+right)\n",
    "            return root.val+max(left, right)\n",
    "\n",
    "        maxSum = [-1001]\n",
    "        dfs(root, maxSum)\n",
    "        return maxSum[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        maxSum = [-99999999]\n",
    "        self.dfs(root, maxSum)\n",
    "        return maxSum[0]\n",
    "    \n",
    "    def dfs(self, root, maxSum):\n",
    "        if not root:\n",
    "            return 0\n",
    "        max_left = [-99999999]\n",
    "        left = max(0, self.dfs(root.left, max_left))\n",
    "        max_right = [-99999999]\n",
    "        right = max(0, self.dfs(root.right, max_right))\n",
    "        maxSum[0] = max(max_left[0], max_right[0])\n",
    "        maxSum[0] = max(maxSum[0], root.val + left + right)\n",
    "\n",
    "        return root.val + max(left, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        maxsum = [-1000]\n",
    "        def dfs(node, maxsum):\n",
    "            if not node:\n",
    "                return 0\n",
    "            sumleft = [-1000]\n",
    "            left = max(0, dfs(node.left, sumleft))\n",
    "            sumright = [-1000]\n",
    "            right = max(0,dfs(node.right, sumright))\n",
    "            maxsum[0] = max(sumleft[0], sumright[0])\n",
    "            maxsum[0] = max(maxsum[0], node.val + left + right)\n",
    "            return node.val + max(left, right)\n",
    "        dfs(root,maxsum)\n",
    "        return maxsum[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        def dfs(root, res):\n",
    "            # 后序遍历\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left_res = [-2**31]\n",
    "            left = max(0, dfs(root.left, left_res))\n",
    "            right_res = [-2**31]\n",
    "            right = max(0, dfs(root.right, right_res))\n",
    "            res[0] = max(left_res[0], right_res[0], root.val + left + right)\n",
    "            return root.val + max(left, right)\n",
    "        res = [-2**31]\n",
    "        dfs(root, res)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class DfsResult:\n",
    "    end_with_self: int\n",
    "    any_path: int\n",
    "\n",
    "    def __init__(self, end_with_self, any_path):\n",
    "        self.end_with_self = end_with_self\n",
    "        self.any_path = any_path\n",
    "\n",
    "    def to_str(self):\n",
    "        return f\"({self.end_with_self}, {self.any_path})\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, node: TreeNode) -> DfsResult:\n",
    "        if not node:\n",
    "            return None\n",
    "        lr = self.dfs(node.left)\n",
    "        rr = self.dfs(node.right)\n",
    "        l_end_with_self = lr.end_with_self if lr else 0\n",
    "        r_end_with_self = rr.end_with_self if rr else 0\n",
    "\n",
    "        end_with_self = max(l_end_with_self + node.val, r_end_with_self + node.val, node.val)\n",
    "        any_path = max(l_end_with_self + node.val + r_end_with_self, end_with_self, node.val)\n",
    "        #print(\"*\" * 100)\n",
    "        #print(node.val)\n",
    "        if lr:\n",
    "            #print(lr.to_str())\n",
    "            any_path = max(any_path, lr.any_path, l_end_with_self)\n",
    "        if rr:\n",
    "            #print(rr.to_str())\n",
    "            any_path = max(any_path, rr.any_path, r_end_with_self)\n",
    "\n",
    "        return DfsResult(end_with_self, any_path)\n",
    "    \n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        ret = self.dfs(root)\n",
    "        return max(ret.end_with_self, ret.any_path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.max_path_sum_impl(root, 0)[1]\n",
    "\n",
    "    def max_path_sum_impl(\n",
    "        self,\n",
    "        root: Optional[TreeNode],\n",
    "        temp_sum: int,\n",
    "    ) -> List[int]:\n",
    "        if root.left is None and root.right is None:\n",
    "            return [temp_sum + root.val, root.val]\n",
    "        # max_root_to_leaf_sum = temp_sum + root.val\n",
    "        max_path_sum = root.val\n",
    "        left = [-1000000000, -1000000000]\n",
    "        if root.left is not None:\n",
    "            left = self.max_path_sum_impl(root.left, temp_sum + root.val)\n",
    "            max_path_sum += max(0, left[0] - temp_sum - root.val)\n",
    "        right = [-1000000000, -1000000000]\n",
    "        if root.right is not None:\n",
    "            right = self.max_path_sum_impl(root.right, temp_sum + root.val)\n",
    "            max_path_sum += max(0, right[0] - temp_sum - root.val)\n",
    "        return [\n",
    "            max(temp_sum + root.val, left[0], right[0]),\n",
    "            max(max_path_sum, left[1], right[1]),\n",
    "        ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxValRecord = {}\n",
    "\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            leftMax = self.maxValPath(root.left)\n",
    "            rightMax = self.maxValPath(root.right)\n",
    "            includeRootMax = max(root.val, root.val+leftMax, root.val+rightMax, root.val+leftMax+rightMax)\n",
    "            RootLeftMax = self.maxPathSum(root.left)\n",
    "            RootRightMax = self.maxPathSum(root.right)\n",
    "            # print(root.val, includeRootMax, RootLeftMax, RootRightMax)\n",
    "            res = includeRootMax\n",
    "            if root.left:\n",
    "                res = max(res, RootLeftMax)\n",
    "            if root.right:\n",
    "                res = max(res, RootRightMax)\n",
    "            return res\n",
    "\n",
    "    def maxValPath(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        if root in self.maxValRecord:\n",
    "            return self.maxValRecord[root]\n",
    "        else:\n",
    "            leftMax = self.maxValPath(root.left)\n",
    "            rightMax = self.maxValPath(root.right)\n",
    "            self.maxValRecord[root] = max(root.val, root.val+leftMax, root.val+rightMax)\n",
    "            return self.maxValRecord[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxValRecord = {}\n",
    "\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            leftMax = self.maxValPath(root.left)\n",
    "            rightMax = self.maxValPath(root.right)\n",
    "            includeRootMax = max(root.val, root.val+leftMax, root.val+rightMax, root.val+leftMax+rightMax)\n",
    "            RootLeftMax = self.maxPathSum(root.left)\n",
    "            RootRightMax = self.maxPathSum(root.right)\n",
    "            # print(root.val, includeRootMax, RootLeftMax, RootRightMax)\n",
    "            res = includeRootMax\n",
    "            if root.left:\n",
    "                res = max(res, RootLeftMax)\n",
    "            if root.right:\n",
    "                res = max(res, RootRightMax)\n",
    "            return res\n",
    "\n",
    "    def maxValPath(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        if root in self.maxValRecord:\n",
    "            return self.maxValRecord[root]\n",
    "        else:\n",
    "            leftMax = self.maxValPath(root.left)\n",
    "            rightMax = self.maxValPath(root.right)\n",
    "            self.maxValRecord[root] = max(root.val, root.val+leftMax, root.val+rightMax)\n",
    "            return self.maxValRecord[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxValRecord = {}\n",
    "\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            leftMax = self.maxValPath(root.left)\n",
    "            rightMax = self.maxValPath(root.right)\n",
    "            includeRootMax = max(root.val, root.val+leftMax, root.val+rightMax, root.val+leftMax+rightMax)\n",
    "            RootLeftMax = self.maxPathSum(root.left)\n",
    "            RootRightMax = self.maxPathSum(root.right)\n",
    "            # print(root.val, includeRootMax, RootLeftMax, RootRightMax)\n",
    "            res = includeRootMax\n",
    "            if root.left:\n",
    "                res = max(res, RootLeftMax)\n",
    "            if root.right:\n",
    "                res = max(res, RootRightMax)\n",
    "            return res\n",
    "\n",
    "    def maxValPath(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        if root in self.maxValRecord:\n",
    "            return self.maxValRecord[root]\n",
    "        else:\n",
    "            leftMax = self.maxValPath(root.left)\n",
    "            rightMax = self.maxValPath(root.right)\n",
    "            self.maxValRecord[root] = max(root.val, root.val+leftMax, root.val+rightMax)\n",
    "            return self.maxValRecord[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: TreeNode) -> int:\n",
    "        tree_max={}\n",
    "        tree_nmax={}\n",
    "        node_list=[]\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        while len(q)!=0:\n",
    "            p=q.pop()\n",
    "            if p!=None:\n",
    "                tree_max[p]=p.val\n",
    "                tree_nmax[p]=p.val\n",
    "                node_list.append(p)\n",
    "                q.append(p.left)\n",
    "                q.append(p.right)\n",
    "        \n",
    "        node_num=len(node_list)\n",
    "\n",
    "        for i in range(node_num-1,-1,-1):\n",
    "            node=node_list[i]\n",
    "            left=tree_nmax[node.left] if node.left!=None else 0\n",
    "            right=tree_nmax[node.right] if node.right!=None else 0\n",
    "\n",
    "            tree_nmax[node]=max(tree_nmax[node],node.val+left,node.val+right)\n",
    "            tree_max[node]=max(tree_nmax[node],node.val+left+right)\n",
    "        return max(tree_max.values())\n",
    "                \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
